package chapter03;

import java.io.FileInputStream;
import java.util.Scanner;

public class test {

    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n;
        int[][] fee;
        try{
            input=new Scanner(new FileInputStream("G:\\boat1.txt"));
        }catch(Exception e){

        }
        while (input.hasNext()){
            n = input.nextInt();
            fee = new int[n][n];

            for(int row=0; row<n-1; row++) {
                for (int col = row + 1; col < n; col++) {
                    fee[row][col] = input.nextInt();
                }
            }

            for(int k=2; k<n; k++) {
                for (int i = 0; i < n - k; i++) {
                    int j = i + k;
                    for (int p = i + 1; p < j; p++) {
                        int tmp = fee[i][p] + fee[p][j];
                        if (fee[i][j] > tmp)
                            fee[i][j] = tmp;
                    }
                }
            }
            System.out.println(fee[0][n-1]);
            //fee[i][j]: 从第i个出租站到第j个出租站所需的最少租金，可见fee[0][n-1]即为所求
        }
    }


}


